package algorithm.swordoff;

/**
 * 数组中数字出现的次数
 * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 * 退化: 一个数组,只有1个数字出现了一次,其他的都出现了两次,这个你会,现在有两个只出现了1次,你怎么办?
 *
 * 思路: 将原数组分为两组,每组必定只含有出现1次的数字1个,那就需要一个分组规则满足:
 *      1. 一样的数字分组结果一样
 *      2. 唯二的两个元素一定不在一组
 *      由此,分组规则由两个只出现1次的元素异或为1的那一位来分组即可
 *
 * 算法: 遍历第一遍,找到两个只出现1次的元素异或为1的那一位
 *      遍历第二遍,分组的同时组内异或
 *
 * 时间复杂度T(2N),需要创建3个临时变量
 *
 * 补充: 异或运算
 *      交换律 a^b = b^a
 *      结合律 a^(b^c) = (a^b)^c
 *      恒等率 a^0 = a
 *      归零率 a^a = 0
 */

public class SQ56_1 {

    public int[] singleNumbers(int[] nums) {
        int ab = 0, k = 0, a = 0, b = 0;
        for (int num : nums) ab ^= num;

        // 找到两个只出现1次的元素异或为1的那一位
        while ((ab & 1) == 0) {
            ab >>= 1;
            k++;
        }

        // 分组同时组内异或
        for (int num : nums) {
            if (((num>>k)&1) == 0) a ^= num;
            else b ^= num;
        }
        return new int[]{a, b};
    }
}
